// Package 剑指_Offer_35__复杂链表的复制 main
// @Title 剑指_Offer_35__复杂链表的复制
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-09 12:12
// @Create  2022-02-09 12:12
package main

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

//
//  copyRandomList
//  @Description: 复制带有随机指针的的链表 使用哈希表
//  @param head：链表的头结点
//  @return *Node： 复制后的链表的头结点
//
func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	nodeMap := make(map[*Node]*Node)
	pCopy := head
	temp := head
	for head != nil {
		tpNode := Node{
			head.Val,
			nil,
			nil,
		}
		nodeMap[head] = &tpNode // 对每一个节点进行克隆
		head = head.Next
	}
	for pCopy != nil {
		if _, ok := nodeMap[pCopy]; ok {
			// 处理应有的关系
			nodeMap[pCopy].Next = nodeMap[pCopy.Next]
			// 处理随机值的关系
			nodeMap[pCopy].Random = nodeMap[pCopy.Random]
		}
		pCopy = pCopy.Next
	}
	return nodeMap[temp]
}

//
//  copyRandomListNoHash
//  @Description: 不使用哈希表的方式，来复制带有随机指针的链表
//  @param head：
//  @return *Node：
//
func copyRandomListNoHash(head *Node) *Node {

	return nil
}

func main() {
	p1 := Node{
		Val:    1,
		Next:   nil,
		Random: nil,
	}
	p2 := Node{
		Val:    2,
		Next:   nil,
		Random: nil,
	}
	p3 := Node{
		Val:    3,
		Next:   nil,
		Random: nil,
	}
	p1.Next = &p2
	p2.Next = &p3
	p1.Random = &p3
	p3.Random = &p2
	display(&p1)
	//copyRandomList(&p1)
}

func display(head *Node) [][]int {
	ans := [][]int{}
	for head != nil {
		temp := []int{}
		temp = append(temp, head.Val)
		if head.Random != nil {
			temp = append(temp, head.Random.Val)
		} else {
			temp = append(temp, -1)
		}
		ans = append(ans, temp)
		head = head.Next
	}
	return ans
}
